﻿#include "unit_test.h"
#include <deque>
#include <list>
#include <string>
#include <cassert>

namespace code_01_04
{
    class Pet
    {
    public:
        explicit Pet(const std::string& type);

        virtual ~Pet() = 0; // 防止实例化

        const std::string& type() const;
    private:
        std::string type_;
    };

    Pet::Pet(const std::string& type)
        : type_(type)
    {}

    Pet::~Pet() {}

    const std::string& Pet::type() const
    {
        return type_;
    }

    class Dog : public Pet
    {
    public:
        Dog() : Pet("Dog") {}
    };

    class Cat : public Pet
    {
    public:
        Cat() : Pet("Cat") {}
    };

    // 这个版本用的是书上第一种“错误”方式
    namespace code_01_04_v1
    {
        class DogCatQueue
        {
        public:
            ~DogCatQueue()
            {
                for (auto p : pets_)
                {
                    delete p;
                }
            }

            void add(Dog* dog)
            {
                pets_.push_back(dog);
                dogs_.push_back(dog);
            }

            void add(Cat* cat)
            {
                pets_.push_back(cat);
                cats_.push_back(cat);
            }

            bool isDogEmpty() const
            {
                return dogs_.empty();
            }

            bool isCatEmpty() const
            {
                return cats_.empty();
            }

            Dog* pollDog()
            {
                return static_cast<Dog*>(pollPetFrom(dogs_));
            }

            Cat* pollCat()
            {
                return static_cast<Cat*>(pollPetFrom(cats_));
            }

            Pet* pollPet()
            {
                assert(!pets_.empty());
                // 这里效率会有点低
                if (dynamic_cast<Dog*>(pets_.front()))
                {
                    return pollPetFrom(dogs_);
                }
                else
                {
                    return pollPetFrom(cats_);
                }
            }

        private:
            Pet* pollPetFrom(std::deque<Pet*>& q)
            {
                assert(!pets_.empty() && !q.empty());
                Pet* first = q.front();
                q.pop_front();
                // 这里的查找也不是很高效
                for (auto it = pets_.begin(); it != pets_.end(); ++it)
                {
                    if (*it == first)
                    {
                        pets_.erase(it);
                        break;
                    }
                }
                return first;
            }
        private:
            std::deque<Pet*> pets_;
            std::deque<Pet*> dogs_;
            std::deque<Pet*> cats_;
        };
    }

    // 改进第一种方式效率低下的问题
    // 利用了std::list插入/删除元素时，迭代器不失效的特性
    namespace code_01_04_v2
    {
        class DogCatQueue
        {
            using iterator = std::list<Pet*>::const_iterator;
        public:
            ~DogCatQueue()
            {
                for (auto p : pets_)
                {
                    delete p;
                }
            }

            void add(Dog* dog)
            {
                pets_.push_back(dog);
                dogs_.emplace_back(dog, --pets_.end());
            }

            void add(Cat* cat)
            {
                pets_.push_back(cat);
                cats_.emplace_back(cat, --pets_.end());
            }

            bool isDogEmpty() const
            {
                return dogs_.empty();
            }

            bool isCatEmpty() const
            {
                return cats_.empty();
            }

            Dog* pollDog()
            {
                return static_cast<Dog*>(pollPetFrom(dogs_));
            }

            Cat* pollCat()
            {
                return static_cast<Cat*>(pollPetFrom(cats_));
            }

            Pet* pollPet()
            {
                assert(!pets_.empty());
                Pet* first = pets_.front();
                // 直接通过指针比较判断下一个pet的类型
                if (!dogs_.empty() && dogs_.front().first == first)
                {
                    pollPetFrom(dogs_);
                }
                else
                {
                    pollPetFrom(cats_);
                }
                return first;
            }

        private:
            Pet* pollPetFrom(std::list<std::pair<Pet*, iterator>>& petsList)
            {
                assert(!pets_.empty() && !petsList.empty());
                // 先从单独的队列中删除
                auto p = petsList.front();
                petsList.pop_front();
                // 再从总的队列中删除
                pets_.erase(p.second);
                return p.first;
            }
        private:
            std::list<Pet*> pets_;
            std::list<std::pair<Pet*, iterator>> dogs_;
            std::list<std::pair<Pet*, iterator>> cats_;
        };
    }

    // 时间戳双队列法
    // 但是实际使用时，这里的index有越界的风险，所以逻辑上不如上面的三队列法严谨
    namespace code_01_04_v3
    {
        class DogCatQueue
        {
        public:
            ~DogCatQueue()
            {
                for (auto& p : dogs_)
                {
                    delete p.first;
                }
                for (auto& p : cats_)
                {
                    delete p.first;
                }
            }

            void add(Dog* dog)
            {
                dogs_.emplace_back(dog, ++index_);
            }

            void add(Cat* cat)
            {
                cats_.emplace_back(cat, ++index_);
            }

            bool isDogEmpty() const
            {
                return dogs_.empty();
            }

            bool isCatEmpty() const
            {
                return cats_.empty();
            }

            Dog* pollDog()
            {
                return pollPetFrom(dogs_);
            }

            Cat* pollCat()
            {
                return pollPetFrom(cats_);
            }

            Pet* pollPet()
            {
                assert(!dogs_.empty() || !cats_.empty());
                if (dogs_.empty())
                {
                    return pollPetFrom(cats_);
                }

                if (cats_.empty())
                {
                    return pollPetFrom(dogs_);
                }

                if (dogs_.front().second < cats_.front().second)
                {
                    return pollPetFrom(dogs_);
                }
                else
                {
                    return pollPetFrom(cats_);
                }
            }
        private:
            template <typename T>
            static T* pollPetFrom(std::list<std::pair<T*, int>>& pets)
            {
                assert(!pets.empty());
                auto p = pets.front();
                pets.pop_front();
                return p.first;
            }
        private:
            int index_{ 0 };
            std::list<std::pair<Dog*, int>> dogs_;
            std::list<std::pair<Cat*, int>> cats_;
        };
    }

    template <typename Queue>
    void DogCatQueueAddDog()
    {
        Dog* dog = new Dog();
        Queue q;
        ASSERT_EQ(true, q.isDogEmpty());

        q.add(dog);
        ASSERT_EQ(false, q.isDogEmpty());

        ASSERT_EQ(dog, q.pollDog());
        ASSERT_EQ(true, q.isDogEmpty());

        delete dog;
    }

    TEST(DogCatQueueAddDog)
    {
        DogCatQueueAddDog<code_01_04_v1::DogCatQueue>();
        DogCatQueueAddDog<code_01_04_v2::DogCatQueue>();
        DogCatQueueAddDog<code_01_04_v3::DogCatQueue>();
    }

    template <typename Queue>
    void DogCatQueueAddCat()
    {
        Cat* cat = new Cat();
        Queue q;
        ASSERT_EQ(true, q.isCatEmpty());

        q.add(cat);
        ASSERT_EQ(false, q.isCatEmpty());

        ASSERT_EQ(cat, q.pollCat());
        ASSERT_EQ(true, q.isCatEmpty());

        delete cat;
    }

    TEST(DogCatQueueAddCat)
    {
        DogCatQueueAddCat<code_01_04_v1::DogCatQueue>();
        DogCatQueueAddCat<code_01_04_v2::DogCatQueue>();
        DogCatQueueAddCat<code_01_04_v3::DogCatQueue>();
    }

    template <typename Queue>
    void DogCatQueueAddPet()
    {
        Cat* cat = new Cat();
        Dog* dog = new Dog();

        Queue q;
        q.add(cat);
        q.add(dog);

        // 弹出cat，dog还在
        ASSERT_EQ(static_cast<Pet*>(cat), q.pollPet());
        ASSERT_EQ(true, q.isCatEmpty());
        ASSERT_EQ(false, q.isDogEmpty());

        // 弹出dog，两者都为空
        ASSERT_EQ(static_cast<Pet*>(dog), q.pollPet());
        ASSERT_EQ(true, q.isDogEmpty());
        ASSERT_EQ(true, q.isCatEmpty());

        delete cat;
        delete dog;
    }

    TEST(DogCatQueueAddPet)
    {
        DogCatQueueAddPet<code_01_04_v1::DogCatQueue>();
        DogCatQueueAddPet<code_01_04_v2::DogCatQueue>();
        DogCatQueueAddPet<code_01_04_v3::DogCatQueue>();
    }
}
